Communication network management and services have been under tremendous transformation. With rapid development of Software-Defined Networking (SDN) and the Internet of Things (IoT), billions of new devices are required to be supported seamlessly and dynamically, and new services are thus imposing much more control and management duty than ever before. Path Computation Element (PCE) and survivability analysis in network routing are some examples of such services in which shortest path algorithms are at heart of the technology that maintains network robustness, flexibility, economics, and swift responses to demands (e.g., Service Level Agreements (SLAs)).
The classic shortest path issue has been long studied. Assume V the number of nodes, and E the number of edges, in graph G. The well-known Single-Pair Shortest Path (SPSP) algorithms include Dijkstra Algorithm (O(V**2), Bellman-Ford algorithm (O(VE)), and other variant algorithms (around O(E+V*log(V))). The Floyd-Warshall algorithm (O(V**3)) computes all shortest paths for each pair of nodes in the graph. The major issue with the classic Shortest Path (SP) algorithms is that none of the classic algorithms are practically useful if used naively. In particular, it comes when G is a significant large graph (V is at millions or larger) and the completion of SPSP is within seconds. The typical uses of SPSP on large graphs are telecommunication networks, social networking, road networks, etc. Even for communication networks where the number of nodes may not be very large, the computation for SPSP from service provisioning, for example, is required to complete within milliseconds, which is effectively similar to the cases of large graphs. Hard requirements imposed by real world applications motivate seeking new solutions to speed up SPSP computation.